package algorithm.t202110;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/10/18 10:58
 * @description :7道
 *      persever to last
 *      昨夜西风调碧树，独上高楼，望尽天涯路。2021.10.18
 */
public class t20211018 {


    //617.合并二叉树
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            return null;
        } else if (root1 == null) {
            return root2;
        } else if (root2 == null) {
            return root1;
        }

        TreeNode merge = new TreeNode(root1.val + root2.val);
        merge.left = mergeTrees(root1.left, root2.left);
        merge.right = mergeTrees(root1.right, root2.right);

        return merge;

    }

    //116.填充每个节的下一个右侧节点指针
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }

        if (root.left == null) {
            return root;
        }

        root.left.next = root.right;

        if (root.next != null) {
            root.right.next = root.next.left;
        }

        connect(root.left);
        connect(root.right);
        return root;

    }

    //面试题04.01 节点间的通路   有向图-->邻接表
    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        //n表示几个节点。graph为邻接图，start为起始节点，target为目标节点

        //1.先将有向图转为邻接表
        List<Integer>[] adj = new ArrayList[n];

        for (int[] ints : graph) {
            int from = ints[0];
            int to = ints[1];
            if (adj[from] == null) {
                adj[from] = new ArrayList<>();
                adj[from].add(to);
            }
            adj[from].add(to);

        }


        return bfs(n, adj, start, target);
    }

    private boolean bfs(int n, List<Integer>[] adj, int start, int target) {
        //维护一个队列，从0这个节点对应的邻接表访问，将访问过程中0能到达的节点入队列
        LinkedList<Integer> queue = new LinkedList<>();
        queue.offer(start);

        //维护一个数组，对已经入队列的节点，不再重复处理
        boolean[] visited = new boolean[n];
        visited[start] = true;

        while (!queue.isEmpty()) {
            int size = queue.size();

            //不断的从队列中获取节点的可访问链表，对链表上的可访问节点判断是否有target
            for (int i = 0; i < size; i++) {
                int node = queue.poll();//获得起始节点
                List<Integer> list = adj[node];//获取起始节点对应的可访问链表

                if (list == null) {
                    continue;
                }

                for (Integer integer : list) {
                    // 遍历过程中有target则直接返回true, 否则最终返回false
                    if (integer == target) {
                        return true;
                    }

                    // 已经入列的节点，不再重复处理
                    if (visited[integer]) {
                        continue;
                    }

                    visited[integer] = true;

                    // 访问过程中0能到达的节点继续入列
                    queue.add(integer);

                }


            }


        }

        return false;
    }

    //面试题04.02 最小高度树
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null) {
            return null;
        } else if (nums.length == 1) {
            return new TreeNode(nums[0]);
        }


        return dfs(nums, 0, nums.length - 1);
    }

    private TreeNode dfs(int[] nums, int l, int r) {

        if (l > r) {
            return null;
        }

        int mid = l + r >> 1;
        TreeNode root = new TreeNode(nums[mid]);

        root.left = dfs(nums, l, mid - 1);
        root.right = dfs(nums, mid + 1, r);
        return root;

    }

    //面试题04.03 特定深度节点链表  层序遍历
    public ListNode[] listOfDepth(TreeNode tree) {
        if (tree == null) {
            return null;
        }
        if (tree.left == null && tree.right == null) {
            return new ListNode[]{new ListNode(tree.val)};
        }

        LinkedList<TreeNode> queue = new LinkedList<>();//维护一个队列，
        queue.offer(tree);//将父节点放入队列

        ArrayList<ListNode> res = new ArrayList<>();//树高不能确定，所以不能使用数组（无法确定初始长度。

        ListNode[] lis = new ListNode[2];

        ListNode dummy = new ListNode(0);

        while (!queue.isEmpty()) {
            int size = queue.size();
            ListNode cur = dummy;


            for (int i = 0; i < size; i++) {

                TreeNode node = queue.poll();//拿到父节点

                cur.next = new ListNode(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }

                cur = cur.next;
            }
            res.add(dummy.next);
            dummy.next = null;


        }

        return res.toArray(new ListNode[]{});
    }


    //面试题04.04 检查平衡性
    boolean flag = true;//我们假定他是平衡的

    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }

        getDepth(root);

        return flag;
    }

    private int getDepth(TreeNode node) {
        if (node == null) {
            return 0;
        }
        if (!flag) {
            return 0;
        }

        int left = getDepth(node.left);
        int right = getDepth(node.right);
        if (Math.abs(left - right) > 1) {
            flag = false;
        }
        return Math.max(left, right) + 1;


    }

    boolean legal = true;

    //面试题04.05 合法二叉搜索树
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }

        int exam = root.val;

        binarySearch(root, exam);
        return legal;

    }

    private int binarySearch(TreeNode node, int num) {
        if (node == null) {
            return 0;
        }
        if (node.left == null && node.right == null) {
            return 1;
        } else if (node.left == null && node.right.val <= node.val) {
            legal = false;
            return 0;
        } else if (node.right == null && node.left.val >= node.val) {
            legal = false;
            return 0;
        } else if ((node.left != null && node.left.val >= node.val) || (node.right != null && node.right.val <= node.val)) {
            legal = false;
            return 0;
        }
        binarySearch(node.left, num);
        binarySearch(node.right, num);
        return -1;
    }


    public static void main(String[] args) {

    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }


    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val +
                '}';
    }
}

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {
    }

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
}

//面试题03.06动物收容所
class AnimalShelf {

    Queue<int[]> queue;

    public AnimalShelf() {
        queue = new LinkedList<>();
    }

    //将动物放入收容所，即入队
    public void enqueue(int[] animal) {
        queue.offer(animal);

    }

    //从收容所中随便领养一个最早进入收容所的动物（不在乎动物是狗还是猫
    public int[] dequeueAny() {
        if (queue.isEmpty()) {
            return new int[]{-1, -1};
        } else {
            return queue.poll();
        }

    }

    //从收容所中领养一只最早进入收容所的狗
    public int[] dequeueDog() {
        if (queue.isEmpty()) {
            return new int[]{-1, -1};
        } else {
            //收容所不为空
            for (int[] animal : queue) {
                if (animal[1] == 1) {
                    queue.remove(animal);
                    return animal;
                }

            }

        }
        return new int[]{-1, -1};
    }

    public int[] dequeueCat() {
        if (queue.isEmpty()) {
            return new int[]{-1, -1};
        } else {
            //收容所不为空
            for (int[] animal : queue) {
                if (animal[1] == 0) {
                    queue.remove(animal);
                    return animal;
                }

            }

        }
        return new int[]{-1, -1};
    }
}